P2894 [USACO08FEB]酒店Hotel

这道题明显是线段树的板题，至于考试时因为懒标记的小问题只有20分，我也很无奈。

进入正题，既然要修改查询区间内连续的一段元素，似曾相识的感觉。
我们等价的把空房子看为1，住人的房子看为0。

我们维护三个值: $num$表示这个区间最长的一段连续$'1'$串 ， $lnum$表示这个区间从左端点开始的最长连续$'1'$串 , $rnum$表示这个区间从右端点开始的最长连续$'1'$串。

然后，用f记录区间状态（懒标记），$f=1$表示全为1，$f=0$表示全为0，$f=2$什么都没发生。

然后，就照着线段树的模板写。稍微麻烦一点的是区间修改后的维护与查询操作，下面来讲解一下。

1.区间修改后的维护（$pushup$函数）

在得到两个子区间后，我们需要根据他们得出大区间的信息。（废话）

1.$lnum$，$rnum$

显然，大区间的$lnum$就等于左区间的$lnum$，特殊情况下，当左区间全为1时，大区间的$lnum$等于左区间的长度加上右区间的$lnum$。$rnum$同理。

2.$num$

显然，大区间的$num$可能是两个小区间的$num$的较大值，同时，也可能是由左区间的$rnum$和右区间$lnum$的拼接而成的连续‘1’串。

2.区间查询（$Find$函数）

应该比较好理解，哪个区间足够就查询哪个区间吗，注意输出最小的值，从左到右依次查询。

#include <cstdio>
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f

const int MAXN = 50000;
int n,m;
struct node{
	int l , r , f;
	int num , lnum , rnum;
}Tree[ 4 * MAXN + 5 ];

int Max( int x , int y ) {
	return x > y ? x : y;
}
int Min( int x , int y ) {
	return x < y ? x : y;
}

void Build( int x , int l , int r ) {
	Tree[ x ].l = l , Tree[ x ].r = r , Tree[ x ].f = 2;
	Tree[ x ].lnum = Tree[ x ].rnum = Tree[ x ].num = Tree[ x ].r - Tree[ x ].l + 1;
	if( l == r ) return;
	
	int Mid = ( l + r ) / 2;
	Build( ls , l , Mid );
	Build( rs , Mid + 1 , r );
}
void pushup( int x ) {
	Tree[ x ].lnum = Tree[ ls ].lnum;
	if( Tree[ ls ].num == Tree[ ls ].r - Tree[ ls ].l + 1 ) Tree[ x ].lnum = Tree[ ls ].num + Tree[ rs ].lnum;
	
	Tree[ x ].rnum = Tree[ rs ].rnum;
	if( Tree[ rs ].num == Tree[ rs ].r - Tree[ rs ].l + 1 ) Tree[ x ].rnum = Tree[ rs ].num + Tree[ ls ].rnum;
	
	Tree[ x ].num = Max( Max( Tree[ ls ].num , Tree[ rs ].num ) , Tree[ ls ].rnum + Tree[ rs ].lnum );
}
void pushdown( int x ) {
	if( Tree[ x ].l == Tree[ x ].r )
		return;
	if( Tree[ x ].f == 0 ) {
		Tree[ ls ].num = 0 , Tree[ ls ].f = 0;
		Tree[ rs ].num = 0 , Tree[ rs ].f = 0;
		Tree[ ls ].lnum = Tree[ ls ].rnum = 0;
		Tree[ rs ].lnum = Tree[ rs ].rnum = 0;
		Tree[ x ].f = 2;
	}
	if( Tree[ x ].f == 1 ) {
		Tree[ ls ].num = Tree[ ls ].r - Tree[ ls ].l + 1 , Tree[ ls ].f = 1;
		Tree[ rs ].num = Tree[ rs ].r - Tree[ rs ].l + 1 , Tree[ rs ].f = 1;
		Tree[ ls ].lnum = Tree[ ls ].rnum = Tree[ ls ].num;
		Tree[ rs ].lnum = Tree[ rs ].rnum = Tree[ rs ].num;
		Tree[ x ].f = 2;
	}
}
void Insert( int x , int l , int r , int k ) {
	if( l > Tree[ x ].r || Tree[ x ].l > r )
		return;
	if( l <= Tree[ x ].l && Tree[ x ].r <= r ) {
		Tree[ x ].f = k;
		Tree[ x ].num = k == 1 ? Tree[ x ].r - Tree[ x ].l + 1 : 0;
		Tree[ x ].lnum = Tree[ x ].rnum = Tree[ x ].num;
		return;
	}
	pushdown( x );
	Insert( ls , l , r , k );
	Insert( rs , l , r , k );
	pushup( x );
}
int Find( int x , int k ) {
	if( Tree[ x ].l == Tree[ x ].r ) return Tree[ x ].l;
	pushdown( x );
	if( Tree[ ls ].num >= k ) return Find( ls , k );
	if( Tree[ ls ].rnum + Tree[ rs ].lnum >= k ) return Tree[ ls ].r - Tree[ ls ].rnum + 1;
	if( Tree[ rs ].num >= k ) return Find( rs , k );
}
int main( ) {
	//freopen("hotel.in","r",stdin);
	//freopen("hotel.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	Build( 1 , 1 , n );
	int op,x,d;
	for( int i = 1 ; i <= m ; i ++ ) {
		scanf("%d",&op);
		if( op == 1 ) {
			scanf("%d",&d);
			if( Tree[ 1 ].num < d ) {
				printf("0\n");
				continue;
			}
			int r = Find( 1 , d );
			Insert( 1 , r , r + d - 1 , 0 );
			printf("%d\n",r);
		}
		else if( op == 2 ) {
			scanf("%d %d",&x,&d);
			Insert( 1 , x , x + d - 1 , 1 );
		}
	}
	return 0;
}